home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 028a / unzup41e.zip / UNSHRINK.C < prev    next >
C/C++ Source or Header  |  1990-12-04  |  4KB  |  179 lines
  1. /*---------------------------------------------------------------------------
  2.  
  3.   unshrink.c
  4.  
  5.   Shrinking is a Dynamic Lempel-Ziv-Welch compression algorithm with partial
  6.   clearing.
  7.  
  8.   ---------------------------------------------------------------------------*/
  9.  
  10.  
  11. #include "unzip.h"
  12.  
  13.  
  14. /*************************************/
  15. /*  UnShrink Defines, Globals, etc.  */
  16. /*************************************/
  17.  
  18. /*      MAX_BITS        13   (in unzip.h; defines size of global work area)  */
  19. #define INIT_BITS       9
  20. #define FIRST_ENT       257
  21. #define CLEAR           256
  22. #define GetCode(dest)   READBIT(codesize,dest)
  23.  
  24. static void partial_clear __((void));   /* local prototype */
  25.  
  26. int codesize, maxcode, maxcodemax, free_ent;
  27.  
  28.  
  29.  
  30.  
  31. /*************************/
  32. /*  Function unShrink()  */
  33. /*************************/
  34.  
  35. void unShrink()
  36. {
  37.     register int code;
  38.     register int stackp;
  39.     int finchar;
  40.     int oldcode;
  41.     int incode;
  42.  
  43.  
  44.     /* decompress the file */
  45.     codesize = INIT_BITS;
  46.     maxcode = (1 << codesize) - 1;
  47.     maxcodemax = HSIZE;         /* (1 << MAX_BITS) */
  48.     free_ent = FIRST_ENT;
  49.  
  50.     for (code = maxcodemax; code > 255; code--)
  51.         prefix_of[code] = -1;
  52.  
  53.     for (code = 255; code >= 0; code--) {
  54.         prefix_of[code] = 0;
  55.         suffix_of[code] = code;
  56.     }
  57.  
  58.     GetCode(oldcode);
  59.     if (zipeof)
  60.         return;
  61.     finchar = oldcode;
  62.  
  63.     OUTB(finchar);
  64.  
  65.     stackp = HSIZE;
  66.  
  67.     while (!zipeof) {
  68.         GetCode(code);
  69.         if (zipeof)
  70.             return;
  71.  
  72.         while (code == CLEAR) {
  73.             GetCode(code);
  74.             switch (code) {
  75.  
  76.             case 1:{
  77.                     codesize++;
  78.                     if (codesize == MAX_BITS)
  79.                         maxcode = maxcodemax;
  80.                     else
  81.                         maxcode = (1 << codesize) - 1;
  82.                 }
  83.                 break;
  84.  
  85.             case 2:
  86.                 partial_clear();
  87.                 break;
  88.             }
  89.  
  90.             GetCode(code);
  91.             if (zipeof)
  92.                 return;
  93.         }
  94.  
  95.  
  96.         /* special case for KwKwK string */
  97.         incode = code;
  98.         if (prefix_of[code] == -1) {
  99.             stack[--stackp] = finchar;
  100.             code = oldcode;
  101.         }
  102.         /* generate output characters in reverse order */
  103.         while (code >= FIRST_ENT) {
  104.             if (prefix_of[code] == -1) {
  105.                 stack[--stackp] = finchar;
  106.                 code = oldcode;
  107.             } else {
  108.                 stack[--stackp] = suffix_of[code];
  109.                 code = prefix_of[code];
  110.             }
  111.         }
  112.  
  113.         finchar = suffix_of[code];
  114.         stack[--stackp] = finchar;
  115.  
  116.  
  117.         /* and put them out in forward order, block copy */
  118.         if ((HSIZE - stackp + outcnt) < OUTBUFSIZ) {
  119.             memcpy(outptr, &stack[stackp], HSIZE - stackp);
  120.             outptr += HSIZE - stackp;
  121.             outcnt += HSIZE - stackp;
  122.             stackp = HSIZE;
  123.         }
  124.         /* output byte by byte if we can't go by blocks */
  125.         else
  126.             while (stackp < HSIZE)
  127.                 OUTB(stack[stackp++]);
  128.  
  129.  
  130.         /* generate new entry */
  131.         code = free_ent;
  132.         if (code < maxcodemax) {
  133.             prefix_of[code] = oldcode;
  134.             suffix_of[code] = finchar;
  135.  
  136.             do
  137.                 code++;
  138.             while ((code < maxcodemax) && (prefix_of[code] != -1));
  139.  
  140.             free_ent = code;
  141.         }
  142.         /* remember previous code */
  143.         oldcode = incode;
  144.     }
  145. }
  146.  
  147.  
  148. /******************************/
  149. /*  Function partial_clear()  */
  150. /******************************/
  151.  
  152. static void partial_clear()
  153. {
  154.     register int pr;
  155.     register int cd;
  156.  
  157.     /* mark all nodes as potentially unused */
  158.     for (cd = FIRST_ENT; cd < free_ent; cd++)
  159.         prefix_of[cd] |= 0x8000;
  160.  
  161.     /* unmark those that are used by other nodes */
  162.     for (cd = FIRST_ENT; cd < free_ent; cd++) {
  163.         pr = prefix_of[cd] & 0x7fff;    /* reference to another node? */
  164.         if (pr >= FIRST_ENT)    /* flag node as referenced */
  165.             prefix_of[pr] &= 0x7fff;
  166.     }
  167.  
  168.     /* clear the ones that are still marked */
  169.     for (cd = FIRST_ENT; cd < free_ent; cd++)
  170.         if ((prefix_of[cd] & 0x8000) != 0)
  171.             prefix_of[cd] = -1;
  172.  
  173.     /* find first cleared node as next free_ent */
  174.     cd = FIRST_ENT;
  175.     while ((cd < maxcodemax) && (prefix_of[cd] != -1))
  176.         cd++;
  177.     free_ent = cd;
  178. }
  179.